package exercises.newcoder.solution;

/**
 * <a href="https://www.nowcoder.com/practice/459bd355da1549fa8a49e350bf3df484?tpId=188&&tqId=38594&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking">
 * NC19 连续子数组的最大和</a>
 *
 * <p><span color="#87CEEB">描述:</span>
 * 输入一个长度为n的整型数组a，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为 O(n).
 * <p>
 * 提示:
 * 1 <= n <= 500
 * -100 <= a[i] <= 100
 * <p>
 * 示例1
 * 输入：
 * [1,-2,3,10,-4,7,2,-5]
 * 返回值：
 * 18
 * <p>
 * 说明：
 * 输入的数组为{1,-2,3,10,-4,7,2,-5}，和最大的子数组为{3,10,-4,7,2}，因此输出为该子数组的和 18。
 *
 * @author or2
 * @date 2021年09月27日 时间: 8:00
 */
public class FindGreatestSumOfSubArray {
    public int FindGreatestSumOfSubArray(int[] array) {
        int ans = array[0];
        for (int i = 1, arrayLength = array.length; i < arrayLength; i++) {
            /*计算累加和*/
            if (array[i-1] > 0) {
                array[i] += array[i-1];
                /*更新累加和*/
                if (array[i] < 0)
                    array[i] = 0;
            }

            /*更新答案*/
            if (array[i] > ans)
                ans = array[i];
        }

        return ans;
    }
}
